#include "Str.h"

#include <assert.h>
#include <string.h>
#include <unicode/ustring.h>
#include <fan-llvm/core/Core.h>
#include "ArgErr.h"
#include "Charset.h"
#include "Decimal.h"
#include "FanBool.h"
#include "FanFloat.h"
#include "FanInt.h"
#include "Func.h"
#include "IndexErr.h"
#include "List.h"
#include "Range.h"
#include "StrBuf.h"
#include "StrInStream.h"
#include "Type.h"
#include "UnsupportedErr.h"
#include "Uri.h"


#define kNumSpacesStrs     20
#define kMaxParamsInFormat 32

static Str* kEmptyStr;
static Str* kNullStr;
static Str* kPercentStr;
static Str* kSpacesStrs[kNumSpacesStrs];
static Str* kXmlEsc['>' + 1];

static Str* Str_splitStr(Str* self, Int s, Int e, Bool trim);
static List* Str_splitWhitespaces(Str* self);

Type* Str_classType = NULL;
VTable* Str_classVTable = NULL;


/**********************************************
 *
 * Methods and fields
 *
 **********************************************/


/* Bool equals(Obj? obj) */
Bool Str_equals(Obj self, NullableObj obj)
{
  if (!VAL_IS_NULL(obj) && Obj_typeof(obj) == Str_classType)
  {
    Str* str1 = VAL_GET_REF(self);
    Str* str2 = VAL_GET_REF(obj);
    if (str1 == str2 || (str1->len == str2->len && u_strncmp(str1->buffer, str2->buffer, str1->len) == 0))
      return TRUE;
  }
  return FALSE;
}


/* Int compare(Obj obj) */
Int Str_compare(Obj self, Obj obj)
{
  if (Obj_typeof(obj) == Str_classType)
  {
    Str* str1 = VAL_GET_REF(self);
    Str* str2 = VAL_GET_REF(obj);

    if (str1 == str2)
      return 0;

    Int len = (str1->len < str2->len) ? str1->len : str2->len;
    for (Int i = 0; i < len; i++)
    {
      Char ch1 = str1->buffer[i];
      Char ch2 = str2->buffer[i];

      if (ch1 < ch2)
        return -1;
      else if (ch1 > ch2)
        return 1;
    }

    if (str1->len == str2->len)
      return 0;
    else
      return (str1->len < str2->len) ? -1 : 1;
  }
  else
    return -1;
}


/* Int hash() */
Int Str_hash(Obj self)
{
  Str* str = VAL_GET_REF(self);
  if (str->hash == 0)
  {
    Int hash = 5381;
    for (Int i = 0; i < str->len; i++)
      hash += (hash << 5) + str->buffer[i];
    str->hash = hash;
  }
  return str->hash;
}


/* Str toStr() */
Str* Str_toStr(Obj self)
{
  return VAL_GET_REF(self);
}


/* Str defVal */
Str* Str_defVal(void)
{
  return kEmptyStr;
}


/* Str fromChars(Int[] chars) */
Str* Str_fromChars(List* chars)
{
  if (List_isEmpty(chars))
    return kEmptyStr;

  Str* str = Str_newUninitialized(List_size(chars));
  for (Int i = 0; i < str->len; i++)
    str->buffer[i] = VAL_GET_INT(List_get(chars, i));
  return str;
}


/* Bool equalsIgnoreCase(Str s) */
Bool Str_equalsIgnoreCase(Str* self, Str* s)
{
  if (self == s)
    return TRUE;
  if (self->len != s->len)
    return FALSE;

  for (Int i = 0; i < self->len; i++)
  {
    Char ch1 = self->buffer[i];
    Char ch2 = s->buffer[i];
    if ('A' <= ch1 && ch1 <= 'Z')
      ch1 |= 0x20;
    if ('A' <= ch2 && ch2 <= 'Z')
      ch2 |= 0x20;

    if (ch1 != ch2)
      return FALSE;
  }
  return TRUE;
}


/* Int compareIgnoreCase(Str s) */
Int Str_compareIgnoreCase(Str* self, Str* s)
{
  if (self == s)
    return 0;

  Int len = (self->len < s->len) ? self->len : s->len;
  for (Int i = 0; i < len; i++)
  {
    Char ch1 = self->buffer[i];
    Char ch2 = s->buffer[i];
    if ('A' <= ch1 && ch1 <= 'Z')
      ch1 |= 0x20;
    if ('A' <= ch2 && ch2 <= 'Z')
      ch2 |= 0x20;

    if (ch1 < ch2)
      return -1;
    else if (ch1 > ch2)
      return 1;
  }

  if (self->len == s->len)
    return 0;
  else
    return (self->len < s->len) ? -1 : 1;
}


/* Str toLocale() */
Str* Str_toLocale(Str* self)
{
  return self;
}


/* Bool isEmpty() */
Bool Str_isEmpty(Str* self)
{
  return (self->len == 0);
}


/* Int size() */
Int Str_size(Str* self)
{
  return self->len;
}


/* Str intern() */
Str* Str_intern(Str* self)
{
  exceptionThrow(UnsupportedErr_newWithFormattedMsg("sys::Str.intern not implemented yet"));
  return NULL;
}


/* Bool startsWith(Str s) */
Bool Str_startsWith(Str* self, Str* s)
{
  return (s->len <= self->len && u_strncmp(self->buffer, s->buffer, s->len) == 0);
}


/* Bool endsWith(Str s) */
Bool Str_endsWith(Str* self, Str* s)
{
  Int offset = self->len - s->len;
  return (s >= 0 && u_strncmp(self->buffer + offset, s->buffer, s->len) == 0);
}


/* Int? index(Str s, Int offset) */
NullableInt Str_index_1(Str* self, Str* s)
{
  return Str_index(self, s, 0);
}


/* Int? index(Str s, Int offset) */
NullableInt Str_index(Str* self, Str* s, Int offset)
{
  if (offset < 0)
    offset += self->len;
  if (offset < 0 || offset >= self->len)
    return VAL_NULL;

  Char* firstOccurence = u_strFindFirst(self->buffer + offset, self->len - offset, s->buffer, s->len);
  if (firstOccurence != NULL)
    return VAL_MAKE_INT(firstOccurence - self->buffer);
  else
    return VAL_NULL;
}


/* Int? indexr(Str s, Int offset) */
NullableInt Str_indexr_1(Str* self, Str* s)
{
  return Str_indexr(self, s, -1);
}


/* Int? indexr(Str s, Int offset) */
NullableInt Str_indexr(Str* self, Str* s, Int offset)
{
  if (offset < 0)
    offset += self->len;
  if (offset < 0 || offset >= self->len)
    return VAL_NULL;

  Char* lastOccurence = u_strFindLast(self->buffer, offset + 1, s->buffer, s->len);
  if (lastOccurence != NULL)
    return VAL_MAKE_INT(lastOccurence - self->buffer);
  else
    return VAL_NULL;
}


/* Int? indexIgnoreCase(Str s, Int offset) */
NullableInt Str_indexIgnoreCase_1(Str* self, Str* s)
{
  return Str_indexIgnoreCase(self, s, 0);
}


/* Int? indexIgnoreCase(Str s, Int offset) */
NullableInt Str_indexIgnoreCase(Str* self, Str* s, Int offset)
{
  Int len = self->len;
  Int slen = s->len;
  Int r = -1;

  if (len == 0)
    return VAL_NULL;
  if (slen == 0)
    return VAL_MAKE_INT(0);

  if (offset < 0)
    offset += self->len;
  if (offset < 0 || offset >= self->len)
    return VAL_NULL;

  Char first = s->buffer[0];
  for (Int i = offset; i <= len - slen; i++)
  {
    // Test first char
    if (!Int_equalsIgnoreCase(first, self->buffer[i]))
      continue;

    // Test remainder of chars
    r = i;
    for (Int si = 1, vi = i + 1; si < slen; si++, vi++)
    {
      if (!Int_equalsIgnoreCase(s->buffer[si], self->buffer[vi]))
      {
        r = -1;
        break;
      }
    }
    if (r >= 0)
      break;
  }

  if (r < 0)
    return VAL_NULL;
  return VAL_MAKE_INT(r);
}


/* Int? indexrIgnoreCase(Str s, Int offset) */
NullableInt Str_indexrIgnoreCase_1(Str* self, Str* s)
{
  return Str_indexrIgnoreCase(self, s, -1);
}


/* Int? indexrIgnoreCase(Str s, Int offset) */
NullableInt Str_indexrIgnoreCase(Str* self, Str* s, Int offset)
{
  Int len = self->len;
  Int slen = s->len;
  Int r = -1;

  if (len == 0 || slen > len)
    return VAL_NULL;
  if (slen == 0)
    return VAL_MAKE_INT(self->len - 1);

  if (offset < 0)
    offset += self->len;
  if (offset < 0 || offset >= self->len)
    return VAL_NULL;
  if (offset > len - slen)
    offset = len - slen;

  Char first = s->buffer[0];
  for (Int i = offset; i >= 0; i--)
  {
    // Test first char
    if (!Int_equalsIgnoreCase(first, self->buffer[i]))
      continue;

    // Test remainder of chars
    r = i;
    for (Int si = 1, vi = i + 1; si < slen; si++, vi++)
    {
      if (!Int_equalsIgnoreCase(s->buffer[si], self->buffer[vi]))
      {
        r = -1;
        break;
      }
    }
    if (r >= 0)
      break;
  }

  if (r < 0)
    return VAL_NULL;
  return VAL_MAKE_INT(r);
}


/* Bool contains(Str s) */
Bool Str_contains(Str* self, Str* s)
{
  NullableInt index = Str_index(self, s, 0);
  return !VAL_IS_NULL(index);
}


/* Bool containsChar(Int ch) */
Bool Str_containsChar(Str* self, Int ch)
{
  for (Int i = 0; i < self->len; i++)
  {
    if (self->buffer[i] == ch)
      return TRUE;
  }
  return FALSE;
}


/* Int get(Int index) */
Int Str_get(Str* self, Int index)
{
  Int i = index;
  if (i < 0)
    i += self->len;
  if (i < 0 || i >= self->len)
    exceptionThrow(IndexErr_newWithIndex(index));
  return self->buffer[i];
}


/* Int getSafe(Int index, Int def) */
Int Str_getSafe_1(Str* self, Int index)
{
  return Str_getSafe(self, index, 0);
}


/* Int getSafe(Int index, Int def) */
Int Str_getSafe(Str* self, Int index, Int def)
{
  Int i = index;
  if (i < 0)
    i += self->len;
  if (i < 0 || i >= self->len)
    return def;
  return self->buffer[i];
}


/* Str getRange(Range range) */
Str* Str_getRange(Str* self, Range* range)
{
  Int start = Range_absStart(range, self->len);
  Int end = Range_absEnd(range, self->len);
  return Str_substr(self, start, end + 1);
}


/* Str plus(Obj? obj) */
Str* Str_plus(Str* self, NullableObj obj)
{
  Str* str = VAL_IS_NULL(obj) ? kNullStr : OBJ_VTABLE(obj)->toStr(obj);
  Str* res = Str_newUninitialized(self->len + str->len);
  u_memcpy(res->buffer, self->buffer, self->len);
  u_memcpy(res->buffer + self->len, str->buffer, str->len);
  return res;
}


/* Int[] chars() */
List* Str_chars(Str* self)
{
  if (self->len == 0)
    return Type_emptyList(Int_classType);
  List* chars = List_new(Int_classType, self->len);
  for (Int i = 0; i < self->len; i++)
    List_add(chars, VAL_MAKE_INT(self->buffer[i]));
  return chars;
}


/* Void each(|Int,Int->Void| c) */
void Str_each(Str* self, Func* c)
{
  for (Int i = 0; i < self->len; i++)
    FUNC_VTABLE(c)->call_2(c, VAL_MAKE_INT(self->buffer[i]), VAL_MAKE_INT(i));
}


/* Void eachr(|Int,Int->Void| c) */
void Str_eachr(Str* self, Func* c)
{
  for (Int i = self->len - 1; i >= 0; i--)
    FUNC_VTABLE(c)->call_2(c, VAL_MAKE_INT(self->buffer[i]), VAL_MAKE_INT(i));
}


/* Bool any(|Int,Int->Bool| c) */
Bool Str_any(Str* self, Func* c)
{
  for (Int i = 0; i < self->len; i++)
  {
    Val res = FUNC_VTABLE(c)->call_2(c, VAL_MAKE_INT(self->buffer[i]), VAL_MAKE_INT(i));
    if (VAL_GET_BOOL(res))
      return TRUE;
  }
  return FALSE;
}


/* Bool all(|Int,Int->Bool| c) */
Bool Str_all(Str* self, Func* c)
{
  for (Int i = 0; i < self->len; i++)
  {
    Val res = FUNC_VTABLE(c)->call_2(c, VAL_MAKE_INT(self->buffer[i]), VAL_MAKE_INT(i));
    if (!VAL_GET_BOOL(res))
      return FALSE;
  }
  return TRUE;
}


/* Str spaces(Int n) */
Str* Str_spaces(Int n)
{
  if (n < 0)
    exceptionThrow(ArgErr_newWithFormattedMsg("n < 0"));

  if (n < kNumSpacesStrs)
    return kSpacesStrs[n];
  else
  {
    Str* str = Str_newUninitialized(n);
    u_memset(str->buffer, ' ', n);
    return str;
  }
}


/* Str lower() */
Str* Str_lower(Str* self)
{
  if (self->len == 0)
    return self;

  Str* lowerStr = Str_newUninitialized(self->len);
  for (Int i = 0; i < self->len; i++)
  {
    Char ch = self->buffer[i];
    if ('A' <= ch && ch <= 'Z')
      lowerStr->buffer[i] = ch | 0x20;
    else
      lowerStr->buffer[i] = ch;
  }
  return lowerStr;
}


/* Str upper() */
Str* Str_upper(Str* self)
{
  if (self->len == 0)
    return self;

  Str* upperStr = Str_newUninitialized(self->len);
  for (Int i = 0; i < self->len; i++)
  {
    Char ch = self->buffer[i];
    if ('a' <= ch && ch <= 'z')
      upperStr->buffer[i] = ch & ~0x20;
    else
      upperStr->buffer[i] = ch;
  }
  return upperStr;
}


/* Str capitalize() */
Str* Str_capitalize(Str* self)
{
  if (self->len == 0)
    return self;

  Char ch = self->buffer[0];
  if ('a' <= ch && ch <= 'z')
  {
    Str* capitalizedStr = Str_newUninitialized(self->len);
    capitalizedStr->buffer[0] = ch & ~0x20;
    u_memcpy(capitalizedStr->buffer + 1, self->buffer + 1, self->len - 1);
    return capitalizedStr;
  }
  else
    return self;
}


/* Str decapitalize() */
Str* Str_decapitalize(Str* self)
{
  if (self->len == 0)
    return self;

  Char ch = self->buffer[0];
  if ('A' <= ch && ch <= 'Z')
  {
    Str* capitalizedStr = Str_newUninitialized(self->len);
    capitalizedStr->buffer[0] = ch | 0x20;
    u_memcpy(capitalizedStr->buffer + 1, self->buffer + 1, self->len - 1);
    return capitalizedStr;
  }
  else
    return self;
}


/* Str toDisplayName() */
Str* Str_toDisplayName(Str* self)
{
  if (self->len == 0)
    return self;
  StrBuf* s = StrBuf_new(self->len + 4);

  // Capitalize first word
  Char c = self->buffer[0];
  if ('a' <= c && c <= 'z')
    c &= ~0x20;
  StrBuf_addChar(s, c);

  // Insert spaces before every capital
  Char last = c;
  for (Int i = 1; i < self->len; i++)
  {
    c = self->buffer[i];
    if ('A' <= c && c <= 'Z' && last != '_')
    {
      Char next = (i + 1 < self->len) ? self->buffer[i + 1] : 'Q';
      if (!('A' <= last && last <= 'Z') || !('A' <= next && next <= 'Z'))
        StrBuf_addChar(s, ' ');
    }
    else if ('a' <= c && c <= 'z')
    {
      if ('0' <= last && last <= '9')
      {
        StrBuf_addChar(s, ' ');
        c &= ~0x20;
      }
      else if (last == '_')
        c &= ~0x20;
    }
    else if ('0' <= c && c <= '9')
    {
      if (!('0' <= last && last <= '9'))
        StrBuf_addChar(s, ' ');
    }
    else if (c == '_')
    {
      StrBuf_addChar(s, ' ');
      last = c;
      continue;
    }
    StrBuf_addChar(s, c);
    last = c;
  }

  return StrBuf_toStr(VAL_MAKE_REF(s));
}


/* Str fromDisplayName() */
Str* Str_fromDisplayName(Str* self)
{
  if (self->len == 0)
    return self;
  StrBuf* s = StrBuf_new(self->len);

  Char c = self->buffer[0];
  Char c2 = (self->len == 1) ? 0 : self->buffer[1];
  if (('A' <= c && c <= 'Z') && !('A' <= c2 && c2 <= 'Z'))
    c |= 0x20;
  StrBuf_addChar(s, c);

  Char last = c;
  for (Int i = 1; i < self->len; i++)
  {
    c = self->buffer[i];
    if (c != ' ')
    {
      if (last == ' ' && 'a' <= c && c <= 'z')
        c &= ~0x20;
      StrBuf_addChar(s, c);
    }
    last = c;
  }

  return StrBuf_toStr(VAL_MAKE_REF(s));
}


/* Str justl(Int width) */
Str* Str_justl(Str* self, Int width)
{
  return Str_padr(self, width, ' ');
}


/* Str justr(Int width) */
Str* Str_justr(Str* self, Int width)
{
  return Str_padl(self, width, ' ');
}


/* Str padl(Int width, Int char) */
Str* Str_padl_1(Str* self, Int width)
{
  return Str_padl(self, width, ' ');
}


/* Str padl(Int width, Int char) */
Str* Str_padl(Str* self, Int width, Int ch)
{
  if (self->len <= width)
    return self;
  else
  {
    Str* res = Str_newUninitialized(width);
    u_memset(res->buffer, ch, width - self->len);
    u_memcpy(res->buffer + width - self->len, self->buffer, self->len);
    return res;
  }
}


/* Str padr(Int width, Int char) */
Str* Str_padr_1(Str* self, Int width)
{
  return Str_padr(self, width, ' ');
}


/* Str padr(Int width, Int char) */
Str* Str_padr(Str* self, Int width, Int ch)
{
  if (self->len <= width)
    return self;
  else
  {
    Str* res = Str_newUninitialized(width);
    u_memcpy(res->buffer, self->buffer, self->len);
    u_memset(res->buffer + self->len, ch, width - self->len);
    return res;
  }
}


/* Str reverse() */
Str* Str_reverse(Str* self)
{
  if (self->len <= 1)
    return self;
  else
  {
    Str* res = Str_newUninitialized(self->len);
    for (Int i = 0; i < self->len; i++)
      res->buffer[i] = self->buffer[self->len - i - 1];
    return res;
  }
}


/* Str trim() */
Str* Str_trim(Str* self)
{
  Int s = 0;
  Int e = self->len;
  while (s < e && self->buffer[s] <= ' ')
    s++;
  while (e > s && self->buffer[e - 1] <= ' ')
    e--;
  return Str_substr(self, s, e);
}


/* Str trimStart() */
Str* Str_trimStart(Str* self)
{
  Int s = 0;
  Int e = self->len;
  while (s < e && self->buffer[s] <= ' ')
    s++;
  return Str_substr(self, s, e);
}


/* Str trimEnd() */
Str* Str_trimEnd(Str* self)
{
  Int s = 0;
  Int e = self->len;
  while (e > s && self->buffer[e - 1] <= ' ')
    e--;
  return Str_substr(self, s, e);
}


/* Str[] split(Int? separator, Bool trim) */
List* Str_split_0(Str* self)
{
  return Str_split(self, VAL_NULL, TRUE);
}


/* Str[] split(Int? separator, Bool trim) */
List* Str_split_1(Str* self, NullableInt separator)
{
  return Str_split(self, separator, TRUE);
}


/* Str[] split(Int? separator, Bool trim) */
List* Str_split(Str* self, NullableInt separator, Bool trim)
{
  if (VAL_IS_NULL(separator))
    return Str_splitWhitespaces(self);

  Int sep = VAL_GET_INT(separator);
  List* toks = List_new(Str_classType, 16);

  Int i = 0;
  for (Int j = 0; j < self->len; j++)
  {
    if (self->buffer[i] != sep)
      continue;
    List_add(toks, VAL_MAKE_REF(Str_splitStr(self, i, j, trim)));
    i = j + 1;
  }
  List_add(toks, VAL_MAKE_REF(Str_splitStr(self, i, self->len, trim)));

  return toks;
}


/* [private] Str splitStr(Int s, Int e, Bool trim) */
static Str* Str_splitStr(Str* self, Int s, Int e, Bool trim)
{
  if (trim)
  {
    while (s < e && self->buffer[s] <= ' ')
      s++;
    while (e > s && self->buffer[e - 1] <= ' ')
      e--;
  }
  return Str_substr(self, s, e);
}


/* [private] Str[] splitWhitespaces() */
static List* Str_splitWhitespaces(Str* self)
{
  List* toks = List_new(Str_classType, 16);

  Int len = self->len;
  while (len > 0 && self->buffer[len - 1] <= ' ')
    len--;

  Int i = 0;
  while (i < len && self->buffer[i] <= ' ')
    i++;

  for (Int j = i; j < len; j++)
  {
    if (self->buffer[j] > ' ')
      continue;
    List_add(toks, VAL_MAKE_REF(Str_substr(self, i, j)));
    i = j + 1;

    while (i < len && self->buffer[i] <= ' ')
      i++;
    j = i;
  }
  List_add(toks, VAL_MAKE_REF(Str_substr(self, i, len)));

  return toks;
}


/* Str[] splitLines() */
List* Str_splitLines(Str* self)
{
  List* lines = List_new(Str_classType, 16);

  Int i = 0;
  for (Int j = 0; j < self->len; j++)
  {
    Char c = self->buffer[i];
    if (c == '\n' || c == '\r')
    {
      List_add(lines, VAL_MAKE_REF(Str_substr(self, i, j)));
      i = j + 1;
      if (c == '\r' && i < self->len && self->buffer[i] == '\n')
      {
        i++;
        j++;
      }
    }
  }
  List_add(lines, VAL_MAKE_REF(Str_substr(self, i, self->len)));

  return lines;
}


/* Str replace(Str from, Str to) */
Str* Str_replace(Str* self, Str* from, Str* to)
{
  NullableInt index = Str_index(self, from, 0);
  if (VAL_IS_NULL(index))
    return self;

  StrBuf* s = StrBuf_new(self->len + Int_max(4 * (to->len - from->len), 0));
  Int lastIndex = 0;

  while (!VAL_IS_NULL(index))
  {
    StrBuf_addSubstr(s, self, lastIndex, VAL_GET_INT(index));
    lastIndex = VAL_GET_INT(index) + from->len;
    index = Str_index(self, from, lastIndex);
  }
  StrBuf_addSubstr(s, self, lastIndex, self->len);

  return StrBuf_toStr(VAL_MAKE_REF(s));
}


/* Int numNewlines() */
Int Str_numNewlines(Str* self)
{
  Int numNewLines = 0;
  for (Int i = 0; i < self->len; i++)
  {
    if (self->buffer[i] == '\n')
      numNewLines++;
    else if (self->buffer[i] == '\r')
    {
      numNewLines++;
      if (i + 1 < self->len && self->buffer[i + 1] == '\n')
        i++;
    }
  }
  return numNewLines;
}


/* Bool isAscii() */
Bool Str_isAscii(Str* self)
{
  for (Int i = 0; i < self->len; i++)
  {
    if (self->buffer[i] >= 128)
      return FALSE;
  }
  return TRUE;
}


/* Bool isSpace() */
Bool Str_isSpace(Str* self)
{
  for (Int i = 0; i < self->len; i++)
  {
    Char ch = self->buffer[i];
    if (ch != ' ' && ch != '\t' && ch != '\n' && ch != '\r' && ch != '\f')
      return FALSE;
  }
  return TRUE;
}


/* Bool isUpper() */
Bool Str_isUpper(Str* self)
{
  for (Int i = 0; i < self->len; i++)
  {
    Char ch = self->buffer[i];
    if (!('A' <= ch && ch <= 'Z'))
      return FALSE;
  }
  return TRUE;
}


/* Bool isLower() */
Bool Str_isLower(Str* self)
{
  for (Int i = 0; i < self->len; i++)
  {
    Char ch = self->buffer[i];
    if (!('a' <= ch && ch <= 'z'))
      return FALSE;
  }
  return TRUE;
}


/* Bool isAlpha() */
Bool Str_isAlpha(Str* self)
{
  for (Int i = 0; i < self->len; i++)
  {
    Char ch = self->buffer[i];
    if (!(('a' <= ch && ch <= 'z') || ('A' <= ch && ch <= 'Z')))
      return FALSE;
  }
  return TRUE;
}


/* Bool isAlphaNum() */
Bool Str_isAlphaNum(Str* self)
{
  for (Int i = 0; i < self->len; i++)
  {
    Char ch = self->buffer[i];
    if (!(('a' <= ch && ch <= 'z') || ('A' <= ch && ch <= 'Z') || ('0' <= ch && ch <= '9')))
      return FALSE;
  }
  return TRUE;
}


/* Int localeCompare(Str s) */
Int Str_localeCompare(Str* self, Str* s)
{
  exceptionThrow(UnsupportedErr_newWithFormattedMsg("sys::Str.localeCompare not implemented yet"));
  return 0;
}


/* Str localeLower() */
Str* Str_localeLower(Str* self)
{
  exceptionThrow(UnsupportedErr_newWithFormattedMsg("sys::Str.localeLower not implemented yet"));
  return NULL;
}


/* Str localeUpper() */
Str* Str_localeUpper(Str* self)
{
  exceptionThrow(UnsupportedErr_newWithFormattedMsg("sys::Str.localeUpper not implemented yet"));
  return NULL;
}


/* Str localeCapitalize() */
Str* Str_localeCapitalize(Str* self)
{
  exceptionThrow(UnsupportedErr_newWithFormattedMsg("sys::Str.localeCapitalize not implemented yet"));
  return NULL;
}


/* Str localeDecapitalize() */
Str* Str_localeDecapitalize(Str* self)
{
  exceptionThrow(UnsupportedErr_newWithFormattedMsg("sys::Str.localeDecapitalize not implemented yet"));
  return NULL;
}


/* Bool? toBool(Bool checked) */
NullableBool Str_toBool_0(Str* self)
{
  return Str_toBool(self, TRUE);
}


/* Bool? toBool(Bool checked) */
NullableBool Str_toBool(Str* self, Bool checked)
{
  return Bool_fromStr(self, checked);
}


/* Int? toInt(Int radix, Bool checked) */
NullableInt Str_toInt_0(Str* self)
{
  return Str_toInt(self, 10, TRUE);
}


/* Int? toInt(Int radix, Bool checked) */
NullableInt Str_toInt_1(Str* self, Int radix)
{
  return Str_toInt(self, radix, TRUE);
}


/* Int? toInt(Int radix, Bool checked) */
NullableInt Str_toInt(Str* self, Int radix, Bool checked)
{
  return Int_fromStr(self, radix, checked);
}


/* Float? toFloat(Bool checked) */
NullableFloat Str_toFloat_0(Str* self)
{
  return Str_toFloat(self, TRUE);
}


/* Float? toFloat(Bool checked) */
NullableFloat Str_toFloat(Str* self, Bool checked)
{
  return Float_fromStr(self, checked);
}


/* Decimal? toDecimal(Bool checked) */
Decimal* Str_toDecimal_0(Str* self)
{
  return Str_toDecimal(self, TRUE);
}


/* Decimal? toDecimal(Bool checked) */
Decimal* Str_toDecimal(Str* self, Bool checked)
{
  return Decimal_fromStr(self, checked);
}


/* Str toCode(Int? quote, Bool escapeUnicode) */
Str* Str_toCode_0(Str* self)
{
  return Str_toCode(self, VAL_MAKE_INT('"'), FALSE);
}


/* Str toCode(Int? quote, Bool escapeUnicode) */
Str* Str_toCode_1(Str* self, NullableInt quote)
{
  return Str_toCode(self, quote, FALSE);
}


/* Str toCode(Int? quote, Bool escapeUnicode) */
Str* Str_toCode(Str* self, NullableInt quote, Bool escapeUnicode)
{
  StrBuf* s = StrBuf_new(self->len + 10);

  // Opening quote
  Int q = 0;
  if (!VAL_IS_NULL(quote))
  {
    q = VAL_GET_INT(quote);
    StrBuf_addChar(s, q);
  }

  for (Int i = 0; i < self->len; i++)
  {
    Char c = self->buffer[i];

    // Escape special chars
    switch (c)
    {
      case '\n':
        StrBuf_addChar(s, '\\');
        StrBuf_addChar(s, 'n');
        continue;
      case '\r':
        StrBuf_addChar(s, '\\');
        StrBuf_addChar(s, 'r');
        continue;
      case '\f':
        StrBuf_addChar(s, '\\');
        StrBuf_addChar(s, 'f');
        continue;
      case '\t':
        StrBuf_addChar(s, '\\');
        StrBuf_addChar(s, 't');
        continue;
      case '\\':
        StrBuf_addChar(s, '\\');
        StrBuf_addChar(s, '\\');
        continue;
      case '"':
        if (q == '"')
        {
          StrBuf_addChar(s, '\\');
          StrBuf_addChar(s, '"');
          continue;
        }
        break;
      case '`':
        if (q == '`')
        {
          StrBuf_addChar(s, '\\');
          StrBuf_addChar(s, '`');
          continue;
        }
        break;
      case '\'':
        if (q == '\'')
        {
          StrBuf_addChar(s, '\\');
          StrBuf_addChar(s, '\'');
          continue;
        }
        break;
      case '$':
        StrBuf_addChar(s, '\\');
        StrBuf_addChar(s, '$');
        continue;
    }

    // Normal character
    if (escapeUnicode && c >= 128)
    {
      const char* hex = "0123456789abcdef";
      StrBuf_addChar(s, '\\');
      StrBuf_addChar(s, 'u');
      StrBuf_addChar(s, hex[(c >> 12) & 0x0F]);
      StrBuf_addChar(s, hex[(c >> 8) & 0x0F]);
      StrBuf_addChar(s, hex[(c >> 4) & 0x0F]);
      StrBuf_addChar(s, hex[c & 0x0F]);
    }
    else
      StrBuf_addChar(s, c);
  }

  // Closing quote
  if (q != 0)
    StrBuf_addChar(s, q);

  return StrBuf_toStr(VAL_MAKE_REF(s));
}


/* Str toXml() */
Str* Str_toXml(Str* self)
{
  StrBuf* s = NULL;
  for (Int i = 0; i < self->len; i++)
  {
    Char c = self->buffer[i];
    if (c > '>')
    {
      if (s != NULL)
        StrBuf_addChar(s, c);
    }
    else
    {
      Str* esc = kXmlEsc[c];
      if (esc != NULL && (c != '>' || i == 0 || self->buffer[i - 1] == ']'))
      {
        if (s == NULL)
        {
          s = StrBuf_new(self->len + 12);
          StrBuf_addSubstr(s, self, 0, i);
        }
        StrBuf_add(s, VAL_MAKE_REF(esc));
      }
      else if (s != NULL)
        StrBuf_addChar(s, c);
    }
  }
  if (s == NULL)
    return self;
  return StrBuf_toStr(VAL_MAKE_REF(s));
}


/* Uri toUri() */
Uri* Str_toUri(Str* self)
{
  return Uri_fromStr(self, TRUE);
}


/* InStream in() */
InStream* Str_in(Str* self)
{
  return (InStream*)StrInStream_new(self);
}


/* Buf toBuf(Charset charset) */
Buf* Str_toBuf_0(Str* self)
{
  return Str_toBuf(self, Charset_utf8());
}


/* Buf toBuf(Charset charset) */
Buf* Str_toBuf(Str* self, Charset* charset)
{
  exceptionThrow(UnsupportedErr_newWithFormattedMsg("sys::Str.toBuf not implemented yet"));
  return NULL;
}


/**********************************************
 *
 * Extra methods
 *
 **********************************************/


/* Create a new Str instance and initialize it with the given number of unitialized code-units */
Str* Str_newUninitialized(Int len)
{
  Str* str = (Str*)Obj_allocate(sizeof(Str), Str_classVTable);
  Obj_make(VAL_MAKE_REF(str));
  str->buffer = memoryAlloc(len * sizeof(Char));
  str->cStr = NULL;
  str->len = len;
  str->hash = 0;
  return str;
}


/* Create a new Str instance and initialize it by copying the "len" code-units from the given buffer */
Str* Str_newFromBuffer(Char* buffer, Int len)
{
  Str* str = Str_newUninitialized(len);
  u_memcpy(str->buffer, buffer, len);
  return str;
}


/* Create a new Str instance and initialize it with Str_makeFromCStr(). */
Str* Str_newFromCStr(const char* cStr)
{
  // Determine the UTF16 length (i.e. number of code-units) of the string
  int32_t len;
  UErrorCode errCode = U_ZERO_ERROR;
  u_strFromUTF8(NULL, 0, &len, cStr, -1, &errCode);
  assert(U_SUCCESS(errCode));

  // Copy the UTF8 string to the new Str's buffer
  Str* str = Str_newUninitialized(len);
  u_strFromUTF8(str->buffer, str->len, NULL, cStr, -1, &errCode);
  assert(U_SUCCESS(errCode));

  return str;
}


/* Create a new Str instance and initialize it with the string given by the format and args.
 * It uses the following format:
 *  - %i for integers (i.e. Int)
 *  - %f for floats (i.e. Float)
 *  - %v for value-objects (i.e. Val)
 *  - %r for reference-objects (i.e. all the pointer-objects: Str*, Range*, ...)
 *  - %% to escape '%' */
Str* Str_newWithFormat(const char* format, ...)
{
  va_list args;
  va_start(args, format);
  Str* str = Str_newWithFormatValist(format, args);
  va_end(args);
  return str;
}


/* Create a new Str instance and initialize it with the string given by the format and args.
 * It uses the following format:
 *  - %i for integers (i.e. Int)
 *  - %f for floats (i.e. Float)
 *  - %v for value-objects (i.e. Val)
 *  - %r for reference-objects (i.e. all the pointer-objects: Str*, Range*, ...)
 *  - %% to escape '%' */
Str* Str_newWithFormatValist(const char* format, va_list args)
{
  Str* argStrs[kMaxParamsInFormat];
  Int numArgs = 0;
  Int totalLen = 0;

  // Convert args to Str and determine the total length of the result Str
  for (const char* c = format; c != '\0'; c++)
  {
    if (*c == '%')
    {
      Str* argStr = NULL;
      switch (*(c + 1))
      {
        case 'i':
          argStr = Int_toStr(VAL_MAKE_INT(va_arg(args, Int)));
          break;
        case 'f':
          argStr = Float_toStr(VAL_MAKE_FLOAT(va_arg(args, Float)));
          break;
        case 'v':
        {
          Obj v = va_arg(args, Obj);
          argStr = OBJ_VTABLE(v)->toStr(v);
          break;
        }
        case 'r':
        {
          Obj* r = va_arg(args, Obj*);
          argStr = OBJ_REF_VTABLE(r)->toStr(VAL_MAKE_REF(r));
          break;
        }
        case '%':
          argStr = kPercentStr;
          break;
      }
      assert(argStr != NULL);

      argStrs[numArgs++] = argStr;
      totalLen += argStr->len;
      c++;
    }
    else
      totalLen++;
  }

  // Build the result Str by copying chars and args
  Str* str = Str_newUninitialized(totalLen);
  Int curArg = 0;
  Int i = 0;
  for (const char* c = format; c != '\0'; c++)
  {
    if (*c == '%')
    {
      Str* argStr = argStrs[curArg++];
      u_memcpy(str->buffer + i, argStr->buffer, argStr->len);
      i += argStr->len;
    }
    else
    {
      str->buffer[i] = *c;
      i++;
    }
  }

  return str;
}


/* Get the content of "self" as a '\0'-terminated UTF8 C-string */
const char* Str_cStr(Str* self)
{
  if (self->cStr == NULL)
  {
    // Determine the UTF8 length of the string
    int32_t utfLen;
    UErrorCode errCode = U_ZERO_ERROR;
    u_strToUTF8(NULL, 0, &utfLen, self->buffer, self->len, &errCode);
    assert(U_SUCCESS(errCode));

    // Copy the UTF16 string to the UTF8 buffer
    self->cStr = memoryAlloc((utfLen + 1) * sizeof(char));
    u_strToUTF8(self->cStr, utfLen + 1, NULL, self->buffer, self->len, &errCode);
    assert(U_SUCCESS(errCode));
  }
  return self->cStr;
}


/* Copy the content of "self" into cStr, as a '\0'-terminated UTF8 C-string.
 * Don't copy more than "maxLen" bytes into cStr, including the terminating '\0'.
 * If "self" does not fit into "cStr", the content will be truncated and the function
 * will return false */
Bool Str_fillCStr(Str* self, char* cStr, Int maxLen)
{
  // Copy the UTF16 string to the UTF8 buffer
  UErrorCode errCode = U_ZERO_ERROR;
  u_strToUTF8(cStr, maxLen, NULL, self->buffer, self->len, &errCode);
  assert(U_SUCCESS(errCode));

  if (cStr[maxLen - 1] != '\0')
  {
    cStr[maxLen - 1] = '\0';
    return FALSE;
  }
  else
    return TRUE;
}


/* Return a substring based on the given start position and exclusive-end position */
Str* Str_substr(Str* self, Int start, Int end)
{
  if (start == end)
    return kEmptyStr;
  if (start == 0 && end == self->len)
    return self;
  if (start < 0 || end < start || end > self->len)
    exceptionThrow(IndexErr_newWithFormattedMsg("Range '%i..<%i' out of bounds", start, end));

  Int len = end - start;
  Str* str = Str_newUninitialized(len);
  u_memcpy(str->buffer, self->buffer + start, len);
  return str;
}


/* Return the first occurence of the given character in the string.
 * If the string does not contain the character, return null */
NullableInt Str_indexChar(Str* self, Int ch)
{
  for (Int i = 0; i < self->len; i++)
  {
    if (self->buffer[i] == ch)
      return VAL_MAKE_INT(i);
  }
  return VAL_NULL;
}


/* Return the last occurence of the given character in the string.
 * If the string does not contain the character, return null */
NullableInt Str_rindexChar(Str* self, Int ch)
{
  for (Int i = self->len - 1; i >= 0; i--)
  {
    if (self->buffer[i] == ch)
      return VAL_MAKE_INT(i);
  }
  return VAL_NULL;
}


/**********************************************
 *
 * Type-system functions
 *
 **********************************************/


Type* Str_initType(void)
{
  if (Str_classType == NULL)
  {
    Type* baseType = Obj_initType();
    VTable* vtable = Str_initVTable();
    Type* type = Type_new("Str", baseType, vtable, sizeof(Str), sizeof(StrVTable));
    Type_registerMethodImplementation(type, "all", Str_all, 1);
    Type_registerMethodImplementation(type, "any", Str_any, 1);
    Type_registerMethodImplementation(type, "capitalize", Str_capitalize, 0);
    Type_registerMethodImplementation(type, "chars", Str_chars, 0);
    Type_registerMethodImplementation(type, "compare", Str_compare, 1);
    Type_registerMethodImplementation(type, "compareIgnoreCase", Str_compareIgnoreCase, 1);
    Type_registerMethodImplementation(type, "contains", Str_contains, 1);
    Type_registerMethodImplementation(type, "containsChar", Str_containsChar, 1);
    Type_registerMethodImplementation(type, "decapitalize", Str_decapitalize, 0);
    Type_registerMethodImplementation(type, "each", Str_each, 1);
    Type_registerMethodImplementation(type, "eachr", Str_eachr, 1);
    Type_registerMethodImplementation(type, "endsWith", Str_endsWith, 1);
    Type_registerMethodImplementation(type, "equals", Str_equals, 1);
    Type_registerMethodImplementation(type, "equalsIgnoreCase", Str_equalsIgnoreCase, 1);
    Type_registerMethodImplementation(type, "fromChars", Str_fromChars, 1);
    Type_registerMethodImplementation(type, "fromDisplayName", Str_fromDisplayName, 0);
    Type_registerMethodImplementation(type, "get", Str_get, 1);
    Type_registerMethodImplementation(type, "getRange", Str_getRange, 1);
    Type_registerMethodImplementation(type, "getSafe", Str_getSafe_1, 1);
    Type_registerMethodImplementation(type, "getSafe", Str_getSafe, 2);
    Type_registerMethodImplementation(type, "hash", Str_hash, 0);
    Type_registerMethodImplementation(type, "in", Str_in, 0);
    Type_registerMethodImplementation(type, "index", Str_index_1, 1);
    Type_registerMethodImplementation(type, "index", Str_index, 2);
    Type_registerMethodImplementation(type, "indexIgnoreCase", Str_indexIgnoreCase_1, 1);
    Type_registerMethodImplementation(type, "indexIgnoreCase", Str_indexIgnoreCase, 2);
    Type_registerMethodImplementation(type, "indexr", Str_indexr_1, 1);
    Type_registerMethodImplementation(type, "indexr", Str_indexr, 2);
    Type_registerMethodImplementation(type, "indexrIgnoreCase", Str_indexrIgnoreCase_1, 1);
    Type_registerMethodImplementation(type, "indexrIgnoreCase", Str_indexrIgnoreCase, 2);
    Type_registerMethodImplementation(type, "intern", Str_intern, 0);
    Type_registerMethodImplementation(type, "isAlpha", Str_isAlpha, 0);
    Type_registerMethodImplementation(type, "isAlphaNum", Str_isAlphaNum, 0);
    Type_registerMethodImplementation(type, "isAscii", Str_isAscii, 0);
    Type_registerMethodImplementation(type, "isEmpty", Str_isEmpty, 0);
    Type_registerMethodImplementation(type, "isLower", Str_isLower, 0);
    Type_registerMethodImplementation(type, "isSpace", Str_isSpace, 0);
    Type_registerMethodImplementation(type, "isUpper", Str_isUpper, 0);
    Type_registerMethodImplementation(type, "justl", Str_justl, 1);
    Type_registerMethodImplementation(type, "justr", Str_justr, 1);
    Type_registerMethodImplementation(type, "localeCapitalize", Str_localeCapitalize, 0);
    Type_registerMethodImplementation(type, "localeCompare", Str_localeCompare, 1);
    Type_registerMethodImplementation(type, "localeDecapitalize", Str_localeDecapitalize, 0);
    Type_registerMethodImplementation(type, "localeLower", Str_localeLower, 0);
    Type_registerMethodImplementation(type, "localeUpper", Str_localeUpper, 0);
    Type_registerMethodImplementation(type, "lower", Str_lower, 0);
    Type_registerMethodImplementation(type, "numNewlines", Str_numNewlines, 0);
    Type_registerMethodImplementation(type, "padl", Str_padl_1, 1);
    Type_registerMethodImplementation(type, "padl", Str_padl, 2);
    Type_registerMethodImplementation(type, "padr", Str_padr_1, 1);
    Type_registerMethodImplementation(type, "padr", Str_padr, 2);
    Type_registerMethodImplementation(type, "plus", Str_plus, 1);
    Type_registerMethodImplementation(type, "replace", Str_replace, 2);
    Type_registerMethodImplementation(type, "reverse", Str_reverse, 0);
    Type_registerMethodImplementation(type, "size", Str_size, 0);
    Type_registerMethodImplementation(type, "spaces", Str_spaces, 1);
    Type_registerMethodImplementation(type, "split", Str_split_0, 0);
    Type_registerMethodImplementation(type, "split", Str_split_1, 1);
    Type_registerMethodImplementation(type, "split", Str_split, 2);
    Type_registerMethodImplementation(type, "splitLines", Str_splitLines, 0);
    Type_registerMethodImplementation(type, "startsWith", Str_startsWith, 1);
    Type_registerMethodImplementation(type, "toBool", Str_toBool_0, 0);
    Type_registerMethodImplementation(type, "toBool", Str_toBool, 1);
    Type_registerMethodImplementation(type, "toBuf", Str_toBuf_0, 0);
    Type_registerMethodImplementation(type, "toBuf", Str_toBuf, 1);
    Type_registerMethodImplementation(type, "toCode", Str_toCode_0, 0);
    Type_registerMethodImplementation(type, "toCode", Str_toCode_1, 1);
    Type_registerMethodImplementation(type, "toCode", Str_toCode, 2);
    Type_registerMethodImplementation(type, "toDecimal", Str_toDecimal_0, 0);
    Type_registerMethodImplementation(type, "toDecimal", Str_toDecimal, 1);
    Type_registerMethodImplementation(type, "toDisplayName", Str_toDisplayName, 0);
    Type_registerMethodImplementation(type, "toFloat", Str_toFloat_0, 0);
    Type_registerMethodImplementation(type, "toFloat", Str_toFloat, 1);
    Type_registerMethodImplementation(type, "toInt", Str_toInt_0, 0);
    Type_registerMethodImplementation(type, "toInt", Str_toInt_1, 1);
    Type_registerMethodImplementation(type, "toInt", Str_toInt, 2);
    Type_registerMethodImplementation(type, "toLocale", Str_toLocale, 0);
    Type_registerMethodImplementation(type, "toStr", Str_toStr, 0);
    Type_registerMethodImplementation(type, "toUri", Str_toUri, 0);
    Type_registerMethodImplementation(type, "toXml", Str_toXml, 0);
    Type_registerMethodImplementation(type, "trim", Str_trim, 0);
    Type_registerMethodImplementation(type, "trimEnd", Str_trimEnd, 0);
    Type_registerMethodImplementation(type, "trimStart", Str_trimStart, 0);
    Type_registerMethodImplementation(type, "upper", Str_upper, 0);
    Type_registerFieldImplementation(type, "defVal", Str_defVal, NULL);
    Str_classType = type;
    Str_initStatic();
  }
  return Str_classType;
}


VTable* Str_initVTable(void)
{
  if (Str_classVTable == NULL)
  {
    VTable* vtable = memoryAlloc(sizeof(StrVTable));
    memcpy(vtable, Obj_initVTable(), sizeof(FanObjVTable));
    ((FanObjVTable*)vtable)->compare = Str_compare;
    ((FanObjVTable*)vtable)->equals = Str_equals;
    ((FanObjVTable*)vtable)->hash = Str_hash;
    ((FanObjVTable*)vtable)->toStr = Str_toStr;
    Str_classVTable = vtable;
  }
  return Str_classVTable;
}


void Str_initStatic(void)
{
  kEmptyStr = Str_newUninitialized(0);
  kNullStr = Str_newFromCStr("null");
  kPercentStr = Str_newFromCStr("%");

  for (Int i = 0; i < kNumSpacesStrs; i++)
  {
    kSpacesStrs[i] = Str_newUninitialized(i);
    u_memset(kSpacesStrs[i]->buffer, ' ', i);
  }

  memset(kXmlEsc, 0, ('>' + 1) * sizeof(Str*));
  kXmlEsc['&'] = Str_newFromCStr("&amp;");
  kXmlEsc['<'] = Str_newFromCStr("&lt;");
  kXmlEsc['>'] = Str_newFromCStr("&gt;");
  kXmlEsc['\''] = Str_newFromCStr("&apos;");
  kXmlEsc['"'] = Str_newFromCStr("&quot;");
}
